#pragma once

#include <cassert>
#include <cmath>

namespace solution_029
{

class Solution
{
public:
    int divide(int dividend, int divisor)
    {
        if (dividend == 0)
            return 0;
        if (divisor == 1)
            return dividend;
        if (divisor == -1 && dividend == (int)0x80000000)
            return (int)0x7FFFFFFF;

        auto x = std::abs(static_cast<long long>(dividend));
        auto y = std::abs(static_cast<long long>(divisor));

        bool positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0);

        long long q = 0;
        long long qq = 1;
        long long yy = y;
        while (x >= y) {
            while ((yy << 1) <= x) {
                yy <<= 1;
                qq <<= 1;
            }
            x -= yy;
            q += qq;
            qq = 1;
            yy = y;
        }
        return positive ? q : -q;
    }
};

}  /* namespace solution_029 */
